_ = float('inf')


def dijkstra(owngraph: list[list[int]], graph_lenth: int) -> (list[int], list[int]):
    """
    dijkstra 实现
    :param owngraph: 图列表（矩阵）
    :param graph_lenth: 图的大小
    :return: 前置节点 距离
    """
    distance = [0] * graph_lenth
    flag = [False] * graph_lenth
    prenode = [0] * graph_lenth
    flag[0] = True
    k = 0
    for i in range(graph_lenth):
        distance[i] = owngraph[k][i]

    for j in range(graph_lenth - 1):
        mini = _
        for i in range(graph_lenth):
            if distance[i] < mini and not flag[i]:
                mini = distance[i]
                k = i
        if k == 0:  # 不连通
            return
        flag[k] = True
        for i in range(graph_lenth):
            if distance[i] > distance[k] + owngraph[k][i]:
                distance[i] = distance[k] + owngraph[k][i]
                prenode[i] = k

        print(distance)
    return distance, prenode


if __name__ == '__main__':
    # n = 6
    # graph = [
    #     [0, 6, 3, _, _, _],
    #     [6, 0, 2, 5, _, _],
    #     [3, 2, 0, 3, 4, _],
    #     [_, 5, 3, 0, 2, 3],
    #     [_, _, 4, 2, 0, 5],
    #     [_, _, _, 3, 5, 0],
    # ]
    # dis, pre = dijkstra(graph, len(graph))
    # print(pre)
    # print(dis)
    # graph2 = [
    #     [0, 10, _, _, _, 9, 15],
    #     [10, 0, _, _, _, 2, _],
    #     [_, _, 0, _, 1, _, 10],
    #     [_, _, _, 0, 7, _, _],
    #     [_, _, 1, 7, 0, _, 12],
    #     [9, 2, _, _, _, 0, 3],
    #     [15, _, 10, _, 12, 3, 0]
    # ]
    # dis, pre = dijkstra(graph2, len(graph2))
    # print(pre)
    # print(dis)
    graph3 = [
        [0, 4, 2, 5, _, _, _, _, _, _],
        [_, 0, _, _, 7, 5, _, _, _, _],
        [_, _, 0, _, _, 9, _, _, _, _],
        [_, _, _, 0, 2, _, 7, _, _, _],
        [_, _, _, _, 0, _, _, 4, _, _],
        [_, _, _, _, _, 0, _, _, _, 6],
        [_, _, _, _, _, _, 0, _, 3, _],
        [_, _, _, _, _, _, _, 0, _, 7],
        [_, _, _, _, _, _, _, _, 6, 8],
        [_, _, _, _, _, _, _, _, _, 0]
    ]
    dis, pre = dijkstra(graph3, len(graph3))
    print(pre)
    print(dis)
